import java.util.ArrayList;
// https://leetcode.cn/problems/sliding-window-maximum/
public class MaxSlidingWindow {
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            ArrayList<Integer> res = new ArrayList<>();
            int [] q = new int[100010];
            int hh = 0 ;
            int tt = -1;
            for(int i  = 0 ; i < nums.length ; i++)
            {
                if(i - k + 1 > q[hh]) ++hh;
                while(hh <= tt && nums[q[tt]] <= nums[i]) tt--;
                q[++tt] = i;
                if(i + 1 >= k) res.add(nums[q[hh]]);
            }
            int [] ret = new int[res.size()];
            int idx = 0;
            for(int v : res)
            {
                ret[idx ++] = v;
            }
            return ret;
        }
    }
}
